//#region 买卖股票系列
/**121. 买卖股票的最佳时机 I
 * - 只能买卖一次
 */
export function maxProfit1(prices: number[]): number {
    //贪心 - 买的那天一定是卖的那天之前的最小值。 每到一天，维护那天之前的最小值即可
    let res = 0
    let preMin = prices[0]
    for (let i = 1; i < prices.length; i++) {
        const cur = prices[i]
        res = Math.max(res, cur - preMin)
        if (cur < preMin) preMin = cur
    }
    return res

    //动态规划
    const length = prices.length
    /**dp[i][0] 表示第i天持有股票所得最多现金 ， dp[i][1] 表示第i天不持有股票所得最多现金。  （持有：可能是今天买的，也可能是之前买的，现在在手上） */
    const dp = prices.map<[number, number]>(() => [0, 0])
    dp[0][0] -= prices[0];//如果第0天买股票
    dp[0][1] = 0; //如果第0天不买
    for (let i = 1; i < length; i++) {
        dp[i][0] = Math.max(dp[i - 1][0], -prices[i])
        dp[i][1] = Math.max(dp[i - 1][1], prices[i] + dp[i - 1][0])
    }
    return dp[length - 1][1] //卖出股票肯定比没卖股票钱多，所以选[1] 
};
/**122. 买卖股票的最佳时机 II
 * - 不限次数
 */
export function maxProfit2(prices: number[]): number {
    let res = 0
    for (let i = 1; i < prices.length; i++) {
        const dif = prices[i] - prices[i - 1]
        if (dif > 0) {
            res += dif
        }
    }
    return res

    //动规： 
    const length = prices.length
    /**dp[i][0] 表示第i天持有股票所得最多现金 ， dp[i][1] 表示第i天不持有股票所得最多现金。 
     1. dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]); 
     -                  保持现状      买(在前一天的基础上)
     2. dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i]);  
     -                 保持现状   卖出(原本持有的钱+卖出的钱)
   */
    const dp: number[][] = Array.from({ length }, () => new Array(2).fill(0))
    dp[0][0] -= prices[0];//如果第0天买股票
    dp[0][1] = 0; //如果第0天不买
    for (let i = 1; i < length; i++) {
        dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] - prices[i])
        dp[i][1] = Math.max(dp[i - 1][1], prices[i] + dp[i - 1][0])
    }
    return dp[length - 1][1] //卖出股票肯定比没卖股票钱多，所以选[1] 
}
/**123. 买卖股票的最佳时机 III
 * - 最多两次
 */
export function maxProfit3(prices: number[]): number {
    //重点在于定义dp数组
    const length = prices.length
    /**dp[i][j]中 i表示第i天，j为 [0 - 4] 五个状态，dp[i][j]表示第i天状态j所剩最大现金。
     * - 五个状态：
     * 0. 没有操作 （其实我们也可以不设置这个状态）
     * 1. 第一次持有股票  dp[i][1] = max(dp[i-1][0] - prices[i], dp[i - 1][1]);  （取 买入 和 没操作 的最大值）
     * 2. 第一次不持有股票  dp[i][2] = max(dp[i - 1][1] + prices[i] , dp[i - 1][2])  （取 卖出 和 没操作 的最大值）
     * 3. 第二次持有股票  dp[i][3] = max(dp[i - 1][2] - prices[i] , dp[i - 1][3])  （取 买入 和 没操作 的最大值）
     * 4. 第二次不持有股票  dp[i][4] = max(dp[i - 1][3] + prices[i] , dp[i - 1][4])  （取 卖出 和 没操作 的最大值）
     */
    const dp = prices.map<[number, number, number, number, number]>(() => [0, 0, 0, 0, 0])
    dp[0][1] -= prices[0];//如果第0天买股票
    dp[0][3] -= prices[0]; //如果第0天第二次买 （买卖买）
    for (let i = 1; i < length; i++) {
        dp[i][0] = dp[i - 1][0]
        dp[i][1] = Math.max(dp[i - 1][1], dp[i][0] - prices[i])
        dp[i][2] = Math.max(dp[i - 1][2], dp[i][1] + prices[i])
        dp[i][3] = Math.max(dp[i - 1][3], dp[i][2] - prices[i])
        dp[i][4] = Math.max(dp[i - 1][4], dp[i][3] + prices[i])
    }
    return dp[length - 1][4] //卖出股票肯定比没卖股票钱多，所以选[4] 
}
/**188. 买卖股票的最佳时机 IV
 * - 买卖k次
 */
export function maxProfit4(prices: number[], k: number): number {
    // 写了股票3，这个直接照着改成通用版就可以了

    const kind = 2 * k + 1
    const dp = prices.map(() => new Array<number>(kind).fill(0))
    for (let i = 1; i < kind; i = i + 2) {
        dp[0][i] = -prices[0]
    }

    for (let i = 1; i < prices.length; i++) {
        const p = prices[i];
        for (let j = 1; j < kind; j++) {
            if (j % 2 === 0) {
                dp[i][j] = Math.max(dp[i][j - 1] + p, dp[i - 1][j])
            } else {
                dp[i][j] = Math.max(dp[i][j - 1] - p, dp[i - 1][j])
            }
        }
    }

    return dp[prices.length - 1][kind - 1]
}
/**714. 买卖股票的最佳时机含手续费 */
export function maxProfit5(prices: number[], fee: number): number {
    /**dp[i][0] 表示第i天持有股票所得最多现金 ， dp[i][1] 表示第i天不持有股票所得最多现金。 
        1. dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]); 
        -                  保持现状      买(在前一天的基础上)
        2. dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i] - fee);  
        -                 保持现状   卖出(原本持有的钱+卖出的钱-手续费)
    */
    const dp = prices.map<[number, number]>(() => [0, 0])
    dp[0][0] = -prices[0]
    dp[0][1] = 0 //第一天的1，可以是没买，也可以是买了又卖，但是手续费要钱，所以不买最多钱
    for (let i = 1; i < prices.length; i++) {
        dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] - prices[i])
        dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i] - fee)
    }
    return dp[prices.length - 1][1]
}
/**309. 买卖股票的最佳时机含冷冻期 */
export function maxProfit6(prices: number[]): number {
    /** 
      - dp[i][j]，第i天状态为j，所剩的最多现金为dp[i][j]。
      0. 状态一：(持有)   持有股票状态（今天买入股票，或者是之前就买入了股票然后没有操作，一直持有） 
      1. 状态二：(不持有) 保持卖出股票的状态（两天前就卖出了股票，度过一天冷冻期。或者是前一天就是本状态，一直没操作）
      2. 状态三：(不持有) 今天卖出股票
      3. 状态四：(不持有) 今天为冷冻期状态，但冷冻期状态不可持续，只有一天！
    */
    const dp = prices.map(() => [0, 0, 0, 0])
    dp[0][0] = -prices[0]
    for (let i = 1; i < prices.length; i++) {
        const p = prices[i]
        dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] - p, dp[i - 1][3] - p)//前一天冷冻期、前一天正常、前一天持有
        dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][3])//前一天正常、前一天冷冻期
        dp[i][2] = dp[i - 1][0] + p
        dp[i][3] = dp[i - 1][2]
    }
    return Math.max(...dp[prices.length - 1])
}
//#endregion